int jump[N];
void exkmp() {
    int n = strlen(str + 1);
    jump[1] = n;
    int k = 1;
    while (k + 1 <= n && str[k] == str[k + 1]) k++;
    jump[2] = k - 1;
    k = 2;
    for (int i = 3; i <= n; i++) {
        if (jump[i - k + 1] + i - 1 < jump[k] + k - 1) jump[i] = jump[i - k + 1];
        else {
            int j = max(0, jump[k] + k - 1 - i);
            while (i + j <= n && str[j + 1] == str[j + i]) j++;
            jump[i] = j;
            k = i;
        }
    }
}
